package commons;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 从数组构建二叉树, 从StackOverflow抄来的
 *
 * @author Jjn
 * @link {<a href="https://stackoverflow.com/questions/37941318/how-to-build-an-incomplete-binary-tree-from-array-representation">How to build an incomplete binary tree from array representation</a>}
 * @since 2022-08-11 9:49
 */
public class BinaryTreeHelper {
    
    public static TreeNode buildTree(List<Integer> array) {
        if (array == null || array.size() == 0) {
            return null;
        }
        
        Queue<TreeNode> treeNodeQueue = new LinkedList<>();
        Queue<Integer> integerQueue = new LinkedList<>();
        for (int i = 1; i < array.size(); i++) {
            integerQueue.offer(array.get(i));
        }
        
        TreeNode treeNode = new TreeNode(array.get(0));
        treeNodeQueue.offer(treeNode);
        
        while (!integerQueue.isEmpty()) {
            Integer leftVal = integerQueue.poll();
            Integer rightVal = integerQueue.isEmpty() ? null : integerQueue.poll();
            TreeNode current = treeNodeQueue.poll();
            if (current == null) {
                return treeNode;
            }
            if (leftVal != null) {
                TreeNode left = new TreeNode(leftVal);
                current.left = left;
                treeNodeQueue.offer(left);
            }
            if (rightVal != null) {
                TreeNode right = new TreeNode(rightVal);
                current.right = right;
                treeNodeQueue.offer(right);
            }
        }
        return treeNode;
    }
}
